﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace text.dfs
{   ///216.找出所有相加之和为 n 的 k 个数的组合。
    //组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
    //输入: k = 3, n = 7
    //输出: [[1,2,4]]
    public class _216
    {
        public IList<IList<int>> CombinationSum3(int k, int n)
        {
            List<IList<int>> res = new List<IList<int>>();
            List<int> path = new List<int>();
            dfs(1,k,n, path,res);
            return res;
        }
        public void dfs(int start,int k,int n,IList<int> path, List<IList<int>> res)
        {
            if (path.Count==k)
            {
                res.Add(new List<int>(path));
                return;
            }
            for (int i = start; i <= 9; i++)
            {
                path.Add(i);
                if (!isValid(path, k, n)) continue;
                dfs(i+1,k,n,path,res);
                path.RemoveAt(path.Count-1);
            }
        }
        public bool isValid(IList<int> path, int k, int n)
        {

            int num = 0;
            foreach (var item in path)
            {
                num += item;
            }
            if ((path.Count == k && num == n) || (path.Count != k && num < n)) return true;
            else {
                path.RemoveAt(path.Count - 1);
                return false;
            } 
        }
    }
}
